<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
#include &lt;cstdlib&gt;
#include &lt;cstdio&gt;

unsigned R() { return (rand() &lt;&lt; 15) + rand(); }

struct tree;
typedef tree * ptree;

struct tree
{
  ptree l, r;
  int x, size;

  tree( int x, ptree l = 0, ptree r = 0 )
  {
    this-&gt;x = x, this-&gt;l = l, this-&gt;r = r;
    size = 1 + Sz(l) + Sz(r);
  }
  friend int Sz( ptree t );
};

inline int Sz( ptree t ) { return t ? t-&gt;size : 0; }

void Split( ptree t, ptree &l, ptree &r, int k ) // size(l) = k
{
  ptree tmp;
  if (!t)
    l = r = 0;
  else if (Sz(t-&gt;l) + 1 &lt;= k)
  {
    Split(t-&gt;r, tmp, r, k - (Sz(t-&gt;l) + 1));
    l = new tree(t-&gt;x, t-&gt;l, tmp);
  }
  else
  {
    Split(t-&gt;l, l, tmp, k);
    r = new tree(t-&gt;x, tmp, t-&gt;r);
  }
}

ptree Merge( ptree l, ptree r )
{
  if (!l)
    return r;
  else if (!r)
    return l;
  else if ((int)(R() % (Sz(l) + Sz(r))) &lt; Sz(l))
    return new tree(l-&gt;x, l-&gt;l, Merge(l-&gt;r, r));
  else
    return new tree(r-&gt;x, Merge(l, r-&gt;l), r-&gt;r);
}

void Out( ptree t )
{
  if (t)
    printf("("), Out(t-&gt;l), printf("%d", t-&gt;x), Out(t-&gt;r), printf(")");
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
